#include"TestGraphAlgorithms.h"
#include"Graph.h"
#include"MakeGraph.h"
#include"GraphAlgorithms.h"
const int NUMBER_OF_TESTS = INT_MAX/100000000;
const int MAX = INT_MAX/100000000;

class DFSTester{
    public:
    DFSTester(int vertices_number) : used(vertices_number, false) {}
    void EnterVertex(int vertex){
        if(used[vertex] == true){
            throw std::logic_error("DepthFirstSearch ERROR : vertex had been visited twice");
        }
        used[vertex] = true;
    }
    void ProcessEdge(int begin_vertex, int end_vertex){
        edge t(begin_vertex, end_vertex);
        processed_edges.insert(t);
    }
    void LeaveVertex(int vertex){        
    }
    std::vector<bool> GetVerticesStatus(){
        return used;
    }
    std::set<edge> GetProcessedEdges(){
        return processed_edges;
    }
private:
    std::vector<bool> used;
    std::set<edge> processed_edges;
};

void TestDepthFirstSearch(){
    for(int test = 0; test < NUMBER_OF_TESTS; test++){
        int vertices_number = rand()%MAX + 1;
        std::vector<edge> edges = MakeRandomEdges(vertices_number);
        std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
        DFSTester tester(vertices_number);
        DepthFirstSearch(*graph, tester);
        std::vector<bool> used = tester.GetVerticesStatus();
        for(int vertex = 0; vertex < vertices_number; vertex++){
            if(!used[vertex]){
                throw std::logic_error("DepthFirstSearch ERROR : not all vertices are visited");
            }
        }
        std::set<edge> all_edges;
        for(int vertex = 0; vertex < vertices_number; vertex++){
            std::set<int> incident_list = graph->GetIncidentList(vertex);
            for(std::set<int>::iterator current_vertex = incident_list.begin(); current_vertex != incident_list.end(); current_vertex++){
                int from = vertex;
                int to = *current_vertex;
                edge t(from, to);
                all_edges.insert(t);
            }
        }
        if(all_edges != tester.GetProcessedEdges()){
            throw std::logic_error("DepthFirstSearch ERROR : not all edges are processed");
        }
    }
}


void TestTopologicalSort(){
    for(int test = 0; test < NUMBER_OF_TESTS;test++){
        int vertices_number = rand()%MAX + 1;
        std::vector<edge> edges = MakeRandomAcyclicGraphEdges( vertices_number);
        std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
        TopologicalSort sort(vertices_number);
        DepthFirstSearch(*graph, sort);
        std::vector<int> sorted_graph = sort.GetSortedGraph();
        std::vector<int> vertex_position(vertices_number);
        for(int position = 0; position < vertices_number; position++){
            vertex_position[sorted_graph[position]] = position;
        }
        for(int vertex = 0; vertex < vertices_number; vertex++){
            std::set<int> incidence_list = graph->GetIncidentList(vertex);
            for(std::set<int>::iterator current_vertex = incidence_list.begin(); current_vertex != incidence_list.end(); current_vertex++){
                int from = vertex;
                int to = *current_vertex;
                if(vertex_position[from] >=  vertex_position[to]){
                    throw std::logic_error("TopologicalSort ERROR : wrong answer");
                }
            }
        }
    }
}

class BFSTester{
    public:
    BFSTester(int vertices_number) : used(vertices_number, false) {}
    void EnterVertex(int vertex){
        if(used[vertex] == true){
            throw std::logic_error("BreadthFirstSearch ERROR : vertex had been visited twice");
        }
        used[vertex] = true;
    }
    void ProcessEdge(int begin_vertex, int end_vertex){
        edge t(begin_vertex, end_vertex);
        processed_edges.insert(t);
    }
    void LeaveVertex(int vertex){        
    }
    std::vector<bool> GetVerticesStatus(){
        return used;
    }
    std::set<edge> GetProcessedEdges(){
        return processed_edges;
    }
private:
    std::vector<bool> used;
    std::set<edge> processed_edges;
};


void TestBreadthFirstSearch(){
    for(int test = 0; test < NUMBER_OF_TESTS; test++){
        int vertices_number = rand()%MAX + 1;
        std::vector<edge> edges = MakeRandomEdges( vertices_number);
        std::auto_ptr<Graph> graph = MakeCompactGraph(vertices_number, edges);
        BFSTester tester(vertices_number);
        BreadthFirstSearch(*graph,tester);
        std::vector<bool> used = tester.GetVerticesStatus();
        for(int vertex = 0; vertex < vertices_number; vertex++){
            if(!used[vertex]){
                throw std::logic_error("BreadthFirstSearch ERROR : not all vertices are visited");
            }
        }
        std::set<edge> all_edges;
        for(int vertex = 0; vertex < vertices_number; vertex++){
            std::set<int> incident_list = graph->GetIncidentList(vertex);
            for(std::set<int>::iterator current_vertex = incident_list.begin(); current_vertex != incident_list.end(); current_vertex++){
                int from = vertex;
                int to = *current_vertex;
                edge t(from, to);
                all_edges.insert(t);
            }
        }
        if(all_edges != tester.GetProcessedEdges()){
            throw std::logic_error("BreadthFirstSearch ERROR : not all edges are processed");
        }
    }
}

void TestAllAlgorithms(){
    TestDepthFirstSearch();
    TestTopologicalSort();
    TestBreadthFirstSearch();
}